#include <algorithm>

using namespace std;

// 一个正整数如果能被 a 或 b 整除，那么它是神奇的。
// 给定三个整数 n , a , b ，返回第 n 个神奇的数字。
// 因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。
// 测试链接 : https://leetcode.cn/problems/nth-magical-number/
// 相似的题目：1201. 丑数 III：https://leetcode.cn/problems/ugly-number-iii/


class Solution
{
private:
    long gcd(long a, long b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }

    long lcm(long a, long b)
    {
        return a / gcd(a, b) * b;
    }

public:
    int nthMagicalNumber(int n, int a, int b) 
    {
        long LCM = lcm(a, b);
        long ans = 0, MOD = 1e9 + 7;
        for(long l = 0, r = (long)n * min(a, b), m = 0; l <= r;)
        {
            m = (l + r) >> 1;
            if(m / a + m / b - m / LCM >= n)
            {
                ans = m;
                r = m - 1;
            }
            else l = m + 1;
        }
        return ans % MOD;
    }
};